package dfs;

import java.util.ArrayList;
import java.util.List;

public class Main2 {

    /**
     * 37. 解数独
     */
    boolean[][] row,col;
    boolean[][][] grid;
    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];

        for(int  i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        dfs(board);
    }
    public boolean dfs(char[][] board) {
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.') {
                    for(int num = 1; num <= 9; num++) {
                        if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) {
                            board[i][j] = (char)('0' + num);
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                            if(dfs(board) == true) return true;
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;
                        }
                    }
                    return false;
                }

            }
        }
        return true;
    }

    /**
     *
     */
    boolean[][] vis;
    int m, n;
    char[] word;
    public boolean exist(char[][] board, String _word)
    {
        m = board.length; n = board[0].length;
        word = _word.toCharArray();
        vis = new boolean[m][n];
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] == word[0])
                {
                    vis[i][j] = true;
                    if(dfs(board, i, j, 1)) return true;
                    vis[i][j] = false;
                }
            }
        return false;
    }
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public boolean dfs(char[][] board, int i, int j, int pos)
    {
        if(pos == word.length)
        {
            return true;
        }
        // 上下左右去匹配 word[pos]
        // 利⽤向量数组，⼀个 for 搞定上下左右四个⽅向
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y]
                    == word[pos])
            {
                vis[x][y] = true;
                if(dfs(board, x, y, pos + 1)) return true;
                vis[x][y] = false;
            }
        }
        return false;
    }



    boolean[][] vis;
    int m, n;
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    int ret;
    public int getMaximumGold(int[][] g)
    {
        m = g.length; n = g[0].length;
        vis = new boolean[m][n];
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(g[i][j] != 0)
                {
                    vis[i][j] = true;
                    dfs(g, i, j, g[i][j]);
                    vis[i][j] = false;
                }
            }
        return ret;
    }
    public void dfs(int[][] g, int i, int j, int path)
    {
        ret = Math.max(ret, path);
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y] !=
                    0)
            {
                vis[x][y] = true;
                dfs(g, x, y, path + g[x][y]);
                vis[x][y] = false;
            }
        }
    }

    /**
     *
     */
    boolean[][] vis;
    int m, n, step;
    int ret;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int uniquePathsIII(int[][] grid)
    {
        m = grid.length; n = grid[0].length;
        vis = new boolean[m][n];
        int bx = 0, by = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(grid[i][j] == 0) step++;
                else if(grid[i][j] == 1)
                {
                    bx = i;
                    by = j;
                }
        step += 2;
        vis[bx][by] = true;
        dfs(grid, bx, by, 1);
        return ret;
    }
    public void dfs(int[][] grid, int i, int j, int count)
    {
        if(grid[i][j] == 2)
        {
            if(count == step)
            {
                ret++;
            }
            return;
        }
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]
                    != -1)
            {
                vis[x][y] = true;
                dfs(grid, x, y, count + 1);
                vis[x][y] = false;
            }
        }
    }


    /**
     *
     */
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m, n;
    int prev;
    public int[][] floodFill(int[][] image, int sr, int sc, int color)
    {
        if(image[sr][sc] == color) return image;
        m = image.length; n = image[0].length;
        prev = image[sr][sc];
        dfs(image, sr, sc, color);
        return image;
    }
    public void dfs(int[][] image, int i, int j, int color)
    {
        image[i][j] = color;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
            {
                dfs(image, x, y, color);
            }
        }
    }

    /**
     *
     */
    boolean[][] vis;
    int m, n;
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    public int numIslands(char[][] grid)
    {
        m = grid.length; n = grid[0].length;
        vis = new boolean[m][n];
        int ret = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(!vis[i][j] && grid[i][j] == '1')
                {
                    ret++;
                    dfs(grid, i, j);
                }
            }
        return ret;
    }
    public void dfs(char[][] grid, int i, int j) {
        vis[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]
                    == '1') {
                dfs(grid, x, y);
            }
        }
    }

    /**
     *
     */
    boolean[][] vis;
    int m, n;
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    int count;
    public int maxAreaOfIsland(int[][] grid)
    {
        m = grid.length; n = grid[0].length;
        vis = new boolean[m][n];
        int ret = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(!vis[i][j] && grid[i][j] == 1)
                {
                    count = 0;
                    dfs(grid, i, j);
                    ret = Math.max(ret, count);
                }
            }
        return ret;
    }
    public void dfs(int[][] grid, int i, int j)
    {
        count++;
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]
                    == 1)
                dfs(grid, x, y);
        }
    }

    /**
     *
     */
    int m, n;
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public void solve(char[][] board)
    {
        m = board.length; n = board[0].length;
        // 1. 先把边界的 O 相连的联通块，全部修改成 '.'
        for(int j = 0; j < n; j++)
        {
            if(board[0][j] == 'O') dfs(board, 0, j);
            if(board[m - 1][j] == 'O') dfs(board, m - 1, j);
        }
        for(int i = 0; i < m; i++)
        {
            if(board[i][0] == 'O') dfs(board, i, 0);
            if(board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }
        // 2. 还原
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] == '.') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
    }
    public void dfs(char[][] board, int i, int j)
    {
        board[i][j] = '.';
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
            {
                dfs(board, x, y);
            }
        }
    }

    /**
     *
     */
    int m, n;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public List<List<Integer>> pacificAtlantic(int[][] h)
    {
        m = h.length; n = h[0].length;
        boolean[][] pac = new boolean[m][n];
        boolean[][] atl = new boolean[m][n];
        // 1. 先处理 pac 洋
        for(int j = 0; j < n; j++) dfs(h, 0, j, pac);
        for(int i = 0; i < m; i++) dfs(h, i, 0, pac);
        // 2. 再处理 atl 洋
        for(int i = 0; i < m; i++) dfs(h, i, n - 1, atl);
        for(int j = 0; j < n; j++) dfs(h, m - 1, j, atl);
// 3. 提取结果
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(pac[i][j] && atl[i][j])
                {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(i); tmp.add(j);
                    ret.add(tmp);
                }

        return ret;
    }
    public void dfs(int[][] h, int i, int j, boolean[][] vis)
    {
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >=
                    h[i][j])
            {
                dfs(h, x, y, vis);
            }
        }
    }

    /**
     *
     */
    int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
    int[] dy = {1, -1, 0, 0, 1, -1, 1, -1};
    int m, n;
    public char[][] updateBoard(char[][] board, int[] click)
    {
        m = board.length; n = board[0].length;
        int x = click[0], y = click[1];
        if(board[x][y] == 'M') // 如果直接点到地雷，游戏结束
        {
            board[x][y] = 'X';
            return board;
        }
        dfs(board, x, y);
        return board;
    }
    public void dfs(char[][] board, int i, int j)
    {
        // 统计⼀下周围地雷的个数
        int count = 0;
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
            {
                count++;
            }
        }
        if(count == 0) // 周围没有地雷
        {
            board[i][j] = 'B';
            for(int k = 0; k < 8; k++)
            {
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
                {
                    dfs(board, x, y);
                }
            }
        }
        else
        {
            board[i][j] = (char)('0' + count);
            return;
        }
    }


    /**
     *
     */
    int m, n, k;
    boolean[][] vis;
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    int ret;
    public int movingCount(int _m, int _n, int _k)
    {
        m = _m; n = _n; k = _k;
        vis = new boolean[m][n];
        dfs(0, 0);
        return ret;
    }
    public void dfs(int i, int j)
    {
        ret++;
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y))
            {
                dfs(x, y);
            }
        }
    }
    public boolean check(int i, int j) {
        int tmp = 0;
        while (i != 0) {
            tmp += i % 10;
            i /= 10;
        }
        while (j != 0) {
            tmp += j % 10;
            j /= 10;
        }
        return tmp <= k;

    }

    /**
     *
     */
    public int uniquePaths(int m, int n)
    {
        // 动态规划
        int[][] dp = new int[m + 1][n + 1];
        dp[1][1] = 1;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                if(i == 1 && j == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        return dp[m][n];
        // 记忆化搜索
        // int[][] memo = new int[m + 1][n + 1];
        // return dfs(m, n, memo);
    }
    public int dfs(int i, int j, int[][] memo)
    {
        if(memo[i][j] != 0)
        {
            return memo[i][j];
        }
        if(i == 0 || j == 0) return 0;
        if(i == 1 && j == 1)
        {
            memo[i][j] = 1;
            return 1;
        }
        memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
        return memo[i][j];
    }





}
